package test230529;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/29 0:32
 * 斐波那契数
 * https://leetcode.cn/problems/fibonacci-number/
 */
public class Solution04 {

    // 动态规划 + 滚动数组空间优化
    // 时间复杂度O(n), 空间复杂度O(1)
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int pre = 0;
        int cur = 1;
        for (int i = 2; i <= n; i++) {
            int num = pre + cur;
            pre = cur;
            cur = num;
        }
        return cur;
    }
}
